package com.moyoutian.leetcode.jianzhi;

import java.util.Arrays;

/**
 * 剑指 Offer 40. 最小的k个数
 * <p>
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [3,2,1], k = 2
 * <p>
 * 输出：[1,2] 或者 [2,1]
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：arr = [0,1,2,1], k = 1
 * <p>
 * 输出：[0]
 * <p>
 * <p>
 * 限制：
 * <p>
 * 0 <= k <= arr.length <= 10000
 * <p>
 * 0 <= arr[i] <= 10000
 */
public class Demo40 {

    public static void main(String[] args) {
        int[] nums = {0, 0, 2, 3, 2, 1, 1, 2, 0, 4};
        System.out.println(Arrays.toString(getLeastNumbers(nums, 10)));
        System.out.println(Arrays.toString(getLeastNumbers1(nums, 10)));
    }

    public static int[] getLeastNumbers1(int[] arr, int k) {
        Arrays.sort(arr);
        int[] re = new int[k];
        for (int i = 0; i < re.length; i++) {
            re[i] = arr[i];
        }
        return re;
    }

    public static int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (k >= arr.length) {
            return arr;
        }
        forkNumbers(arr, k - 1, 0, arr.length - 1);
        int[] re = new int[k];
        for (int i = 0; i < re.length; i++) {
            re[i] = arr[i];
        }
        Arrays.sort(re);
        return re;
    }

    /**
     * 分治
     *
     * @param arr 数组
     * @param k   目标
     */
    public static int[] forkNumbers(int[] arr, int k, int left, int right) {
        int temp_right = right;
        int temp_left = left;
        int temp = arr[right];
        right = right - 1;
        //等于的放在右边
        while (left < right) {
            //左边又移
            while (left < right && arr[left] < temp) {
                left++;
            }
            //右边左移，等值放在右边
            while (left < right && arr[right] >= temp) {
                right--;
            }
            //交换
            sw(arr, left, right);
        }
        if (arr[right] > temp) {
            sw(arr, right, temp_right);
        }
        //小于需在又
        if (right < k) {
            return forkNumbers(arr, k, right + 1, temp_right);
        } else if (right > k) {
            return forkNumbers(arr, k, temp_left, right);
        } else {
            //左边的数据量等于k
            return arr;
        }
    }

    public static void sw(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}
